<?php 
/**
 * 题目：复杂链表的复制
 * 描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
 * 
 */

class RandomListNode{
    public $val;
    public $next = NULL;
    public $random = NULL;
    public function __construct($x){
        $this->val = $x;
    }
}

function cloneList($node)
{
	$node = cloneNodeEctype($node);
	$node = cloneNodeRandomNode($node);
	return reconnectNode($node);
}

/** 
 * 复制节点副本
 * A->B->C->D
 * A->A`->B->B`->C->C`->D->D`
 * @return [type] [description]
 */
function cloneNodeEctype($node)
{
	if ($node != null) {
		$curNode = $node;
		while ($curNode!=null) {
			$cloneNode = new RandomListNode($curNode->val);
			$cloneNode->next = $curNode->next;
			$cloneNode->random = null;
			$curNode->next = $cloneNode;
			$curNode = $cloneNode->next; 
		}
		return $node;
	}
	return null;
}

/**
 * 复制节点的随意指向
 * @return [type] [description]
 */
function cloneNodeRandomNode($node)
{
	if ($node != null) {
		$curNode = $node;
		while ($curNode!=null) {
			$cloneNode = $curNode->next;
			$random = $curNode->random;
			if ($random) {
				$cloneNode->random = $random->next;	
			}
			$curNode = $cloneNode->next;
		}
		return $node;
	}
	return null;
}

/**
 * 拆分节点，根据节点奇偶项拆分
 * @param  [type] $node [description]
 * @return [type]       [description]
 */
function reconnectNode($node)
{
	$cloneHead = null;
	$cloneNode = null;
	$curNode = $node;

	if ($curNode  != null) {
		$cloneHead = $cloneNode = $curNode->next;
		$curNode->next = $cloneNode->next;
		$curNode = $curNode->next;
	}  
    
    while ($curNode!=null) {
		$cloneNode->next = $curNode->next;
		$cloneNode = $cloneNode->next;
		$curNode->next = $cloneNode->next;
		$curNode = $curNode->next;
	}
    return $cloneHead;
}

$node1 = new RandomListNode(1);
$node2 = new RandomListNode(2);
$node3 = new RandomListNode(3);
$node4 = new RandomListNode(4);
$node5 = new RandomListNode(5);
$node6 = new RandomListNode(6);
$node2->random = $node5;
$node1->next = $node2;
$node1->next->next = $node3;
$node4->random = $node2;
$node1->next->next->next = $node4;
$node5->random = $node6;
$node1->next->next->next->next = $node5;
$node5->random = $node1; 
$node1->next->next->next->next->next = $node6;

print_r(cloneList($node1));